class Solution {
public:
    bool isMatch(string s, string p)
    {
        int m = s.size();
        int n = p.size();

        vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
        //dp[0][0]=true;
        s = " " + s;
        p = " " + p;
        dp[0][0] = true;
        for (int i = 1; i <= n; i++)
        {
            if (p[i] == '*')dp[0][i] = true;
            else break;
        }

        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                if (p[i] == s[j] || p[i] == '?')
                {
                    dp[j][i] = dp[j - 1][i - 1];
                }
                else if (p[i] == '*')
                {
                    dp[j][i] = dp[j - 1][i] || dp[j][i - 1];
                }
            }
        }
        return dp[m][n];
    }
};